#leetcode题目208：实现Trie前缀树
#难度：中等，比课程表要简单，本质是二叉树的扩展。


#由于小写的字母只有26个，所以是26叉树。啥是26叉树？就是每个节点有26个子节点，每个子节点对应一个字母。

class TrieNode:
    """Trie节点类"""
    def __init__(self):
        self.children = [None] * 26  # 26个小写字母
        self.is_end_of_word = False  # 标记是否是单词结尾

class Trie:
    """Trie前缀树类"""
    
    def __init__(self):
        """
        初始化Trie
        """
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        """
        插入单词到Trie中
        :param word: 要插入的单词
        """
        curr = self.root
        
        for char in word:
            # 计算字符在数组中的索引
            index = ord(char) - ord('a')
            
            # 如果路径不存在，创建新节点
            if curr.children[index] is None:
                curr.children[index] = TrieNode()
            
            # 移动到下一个节点
            curr = curr.children[index]
        
        # 标记单词结尾
        curr.is_end_of_word = True

    def search(self, word: str) -> bool:
        """
        搜索单词是否在Trie中
        :param word: 要搜索的单词
        :return: 如果单词存在返回True，否则返回False
        """
        curr = self.root
        
        for char in word:
            index = ord(char) - ord('a')
            
            # 如果路径不存在，单词不存在
            if curr.children[index] is None:
                return False
            
            # 移动到下一个节点
            curr = curr.children[index]
        
        # 检查是否是完整单词
        return curr.is_end_of_word
    
    def startsWith(self, prefix: str) -> bool:
        """
        搜索是否有以给定前缀开头的单词
        :param prefix: 要搜索的前缀
        :return: 如果存在以该前缀开头的单词返回True，否则返回False
        """
        curr = self.root
        
        for char in prefix:
            index = ord(char) - ord('a')
            
            # 如果路径不存在，前缀不存在
            if curr.children[index] is None:
                return False
            
            # 移动到下一个节点
            curr = curr.children[index]
        
        # 只要路径存在就返回True
        return True


# 输入
# ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
# [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]，可以翻译成代码就是：
trie = Trie()
print(trie.__init__())
print(trie.insert("apple")) 
print(trie.search("apple"))
print(trie.search("app"))
print(trie.startsWith("app"))
print(trie.insert("app"))
print(trie.search("app"))
# 输出
# [null, null, true, false, true, null, true]
#测试数据


